#pragma once
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>

#include <time.h>
#include <assert.h>

#include <thread>
#include <mutex>
#include <atomic>

using std::cout;
using std::endl;

#if defined(_WIN32) || defined(_WIN64)
#include <windows.h>
#elif __linux__
#include <sys/mman.h>
#endif

#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#endif
#ifdef _WIN32
typedef size_t PAGE_ID;
#elif __linux__
// typedef size_t PAGE_ID;
typedef uintptr_t PAGE_ID;
#endif

static const size_t MAX_BYTES = 256 * 1024; // TLS可以申请的最大内存
// static const size_t PAGE_SHIFT = 12;        // 以8KB页对齐
static const size_t PAGE_SHIFT = 12;        // 以8KB页对齐
static const size_t NFREELIST = 208;
static const size_t NPAGES = 129;

static void *&NextObj(void *obj)
{
    return *(void **)obj;
}
class FreeList
{
public:
    // 头插
    void Push(void *obj)
    {
        assert(obj);
        //*(void**)obj=_freeList;
        NextObj(obj) = _freeList;
        _freeList = obj;
    }
    // 插入一段
    void PushRange(void *start, void *end, size_t n)
    {
        NextObj(end) = _freeList;
        _freeList = start;
        _size += n;
    }
    // 弹出一段
    void PopRange(void *&start, void *&end, size_t n)
    {
        assert(n <= _size);
        start = _freeList;
        end = start;
        for (size_t i = 0; i < n - 1; i++)
        {
            end = NextObj(end);
        }
        _freeList = NextObj(end);
        NextObj(end) = nullptr;
        _size -= n;
    }
    // 头删
    void *Pop()
    {
        assert(_freeList);
        // 头删
        void *obj = _freeList;
        _freeList = NextObj(obj);
        --_size;
        return obj;
    }
    // 判空
    bool Empty()
    {
        return _freeList == nullptr;
    }
    // 最大数量
    size_t &MaxSize()
    {
        return _maxsize;
    }
    // 当前数量
    size_t Size()
    {
        return _size;
    }

private:
    // 链表结构 内存对象的头4/8个字节，存下一个对象的地址
    void *_freeList = nullptr;
    size_t _maxsize = 1;
    size_t _size = 0;
};

class SizeClass
{
    // RoundUp向上对齐得到大小
    // Index向上对齐得到桶号
private:
    static inline size_t _RoundUp(size_t bytes, size_t alignNum)
    {
        return ((bytes + alignNum - 1) & ~(alignNum - 1));
        // 因为当 alignNum = 2ⁿ 时，
        // alignNum-1 正好给出 低 n 位全 1 的掩码
        // ~(alignNum-1) 正好给出 低 n 位全 0 的高位掩码
        // 于是 按位与 就把任何地址 截断（向下对齐）到最近的 2ⁿ 边界
        // 8-1 -> 0000 0111
        // ~7  -> 1111 1000
        // 再加上前面的 + alignNum-1 把原数先推到下一个区间
        // 比如[8,16]那么第4位一定为1 按位与之后只会保留 对齐位
        // 0000 1000 - 0001 0000

        // 理解为 ((bytes+alignNum-1)/alignNum)*alignNum
        // ((7+8)/8)*8=8
        // ((127+8)/8)*8=128
        // 向上取整
    }
    static inline size_t _Index(size_t bytes, size_t align_shift)
    {
        // 向上对齐到 2^align_shift 后减 1 得到桶号
        return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
    }

public:
    // 减少内存碎片
    // [1,128]					8byte对齐	     freelist[0,16)
    // [128+1,1024]				16byte对齐	     freelist[16,72)
    // [1024+1,8*1024]			128byte对齐	     freelist[72,128)
    // [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
    // [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)
    static inline size_t RoundUp(size_t size)
    {
        if (size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if (size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if (size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if (size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if (size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else
        {
            // return _RoundUp(size, 1 << PAGE_SHIFT);
            // 页对齐后，分配器只需 一次系统调用 就能满足 ≥256 KB 的请求
            return _RoundUp(size, 8 * 1024); // linux环境下一页是4096
        }
    }

    static inline size_t Index(size_t bytes)
    {
        assert(bytes <= MAX_BYTES);
        // 每个区间有多少个桶
        static int group_array[4] = {16, 56, 56, 56};
        if (bytes <= 128)
        {
            return _Index(bytes, 3);
            // 对齐8
        }
        else if (bytes <= 1024)
        {
            return _Index(bytes - 128, 4) + group_array[0];
            // 对齐16
            // 128 以内是按 8 字节 步长（bucket 0~15）；
            // 从 129 开始才按 16 字节 步长，因此要把 128 这一整段 扣掉，
            // 让 129 变成 1，从而落在新的 0 号桶里
        }
        else if (bytes <= 8 * 1024)
        {
            return _Index(bytes - 1024, 7) + group_array[0] + group_array[1];
            // 对齐128
        }
        else if (bytes <= 64 * 1024)
        {
            return _Index(bytes - 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
            // 对齐1024
        }
        else if (bytes <= 256 * 1024)
        {
            return _Index(bytes - 64 * 1024, 13) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
            // 对齐8*1024
        }
        else
        {
            assert(-1);
        }
        return -1;
    }
    // 一次thread cache从中心缓存获取多少个
    static size_t NumMoveSize(size_t size)
    {
        assert(size > 0);
        // [2...5]一次批量移动多少个对象的上限值512
        // 小对象一次批量上限高
        // 大对象一次批量上限低
        int num = MAX_BYTES / size;
        if (num < 2)
            num = 2;
        if (num > 512)
            num = 512;
        return num;
    }
    static size_t NumMovePage(size_t size)
    {
        size_t num = NumMoveSize(size);
        size_t npage = num * size;
        npage >> PAGE_SHIFT;
        if (npage == 0)
            npage = 1;
        return npage;
    }
};

struct Span
{
    PAGE_ID _pageId = 0; // 大块内存起始页的页号
    size_t _n = 0;       // 页的数量

    Span *_next = nullptr;
    Span *_prev = nullptr;

    size_t _objSize = 0;
    size_t _useCount = 0;

    void *_freeList = nullptr;
    bool _isUse = false;
};

// 带头双向循环链表
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_next = _head;
        _head->_prev = _head;
    }
    Span *Begin()
    {
        return _head->_next;
    }
    Span *End()
    {
        return _head;
    }
    bool Empty()
    {
        return _head->_next == _head;
    }
    void PushFront(Span *span)
    {
        Insert(Begin(), span);
    }
    Span *PopFront()
    {
        Span *front = _head->_next;
        Erase(front);
        return front;
    }
    void Insert(Span *pos, Span *newSpan)
    {
        assert(pos);
        assert(newSpan);
        Span *prev = pos->_prev;
        // prev newspan pos
        // 插入到prev 和 pos 之间
        prev->_next = newSpan;
        newSpan->_prev = prev;
        newSpan->_next = pos;
        pos->_prev = newSpan;
    }
    void Erase(Span *pos)
    {
        assert(pos);
        assert(pos != _head);
        Span *prev = pos->_prev;
        Span *next = pos->_next;

        // 维护链表结构
        // pos的释放由PageCache管理
        prev->_next = next;
        next->_prev = prev;
    }

private:
    Span *_head;

public:
    std::mutex _mtx; // 桶锁
};
